//package org.wangbao.service;
//
//import java.util.*;
//
//public class Sequence {
//
//
//	/*
//	*merge-sort 划分排序
//	*bubble-sort 冒泡排序
//	*select-sort 选择排序
//	*insert-sort 插入排序
//	*shell-sort shell排序
//	*quick-sort 快速排序
//	*/
//	class Time_record{
//	    private long a;
//	    public Time_record(){}
//	    public void begin(){
//	        a=System.currentTimeMillis();
//	        System.out.println(a);                
//	    }
//	    public void end(){
//	        System.out.println(System.currentTimeMillis());
//	        System.out.println("Cost:"+(System.currentTimeMillis()-a)+" for sorting");        
//	    }        
//	}
//
//
//	class Sort{
//	    public static void display(int s[]){
//	        for(int i:s)
//	            System.out.println(i);
//	    }
//	    public static int[] merge_sort(int s[]){
//	         int n=s.length;
//	         if(s.length==1){
//	             return s;         
//	         }
//	        int s1[];
//	        int s2[];    
//	        int n1=n/2;
//	        int n2=n-n/2;    
//	        int i,j,k; 
//	        s1=new int[n1];
//	         s2=new int[n2];    
//	         for(i=0;i<n1;i++) 
//	             s1[i]=s[i];
//	         for(i=0;i<n2;i++)
//	             s2[i]=s[i+n1];
//	         s1=merge_sort(s1);
//	         s2=merge_sort(s2);
//	         k=0;
//	         i=0;
//	         j=0;
//	         while(i<n1 && j<n2){
//	             if(s1[i]<s2[j]){            
//	                 s[k]=s1[i];
//	                 i++;
//	                 k++;
//	             }
//	             else{
//	                 s[k]=s2[j];
//	                 j++;
//	                 k++;                
//	             }    
//	         }
//	         
//	         while(i<n1){
//	             s[k]=s1[i];
//	             k++;
//	             i++;
//	         }
//	         while(j<n2){
//	             s[k]=s2[j];
//	             k++;
//	             j++;
//	         }
//	       return s;         
//	    }
//	    public static int[] bubble_sort(int s[]){
//	        int n=s.length;
//	        int temp;
//	        for(int i=0;i<n;i++)
//	            for(int j=i+1;j<n;j++)
//	                if(s[j-1]>s[j]){
//	                    temp=s[j-1];
//	                    s[j-1]=s[j];
//	                    s[j]=temp;
//	                }
//	         return s;        
//	    } 
//	    public static int[] select_sort(int s[]){
//	        int n=s.length;
//	        int min_index;
//	        int min_value;
//	        int temp;
//	        for(int i=0;i<n;i++){
//	        min_index=i;
//	        min_value=s[i]; 
//	        for(int j=i+1;j<n;j++)
//	            if(s[j]<min_value){
//	                min_index=j;
//	                 min_value=s[j];                 
//	            }
//	        temp=s[i];
//	        s[i]=min_value;
//	        s[min_index]=temp;        
//	        }
//	        return s;
//	    }
//	    
//	    public static int[] insert_sort(int s[]){
//	       int n=s.length;
//	       int temp;
//	       int i,j,k;
//	       for(i=1;i<n;i++){
//	           for(j=0;j<i;j++){
//	                if (s[j]>s[i])
//	                    break;     
//	           }    
//	           temp=s[i];
//	           for(k=i;j<k;k--)
//	               s[k]=s[k-1];
//	           s[j]=temp;
//	       }    
//	        
//	       return s;    
//	    }
//	    
//	    public static int[] shell_sort(int s[]){
//	        int n=s.length;
//	        int gap=1;
//	        int temp;
//	        while(gap<n)
//	            gap=3*gap+1;
//	        gap=(gap-1)/3;
//	        int i,j,inter,outer;
//	        while(gap>=1){
//	           for(i=0;i<gap;i++){
//	              for(outer=i+gap;outer<n;outer=outer+gap){
//	                temp=s[outer];
//	                for(inter=i;inter<outer;inter=inter+gap) 
//	                if (s[inter]>temp)
//	                    break;    
//	                for(j=outer;j>inter;j=j-gap)
//	                    s[j]=s[j-gap];
//	                s[inter]=temp; 
//	              }
//	           }
//	            gap=(gap-1)/3;
//	        }        
//	        return s;
//	    }
//	    
//
//	    
//	    
//	    
//	    public static int[] quick_sort(int s[]){
//	        return Sort.quicksort(s,0,s.length-1);
//	    }
//	    
//	    
//	    public static int[] quicksort (int[] a, int lo, int hi)
//	{
//	// lo is the lower index, hi is the upper index
//	// of the region of array a that is to be sorted
//	    int i=lo, j=hi, h;
//	    int x=a[(lo+hi)/2];
//
//	    // partition
//	    do
//	    {    
//	        while (a[i]<x) i++; 
//	        while (a[j]>x) j--;
//	        if (i<=j)
//	        {
//	            h=a[i]; a[i]=a[j]; a[j]=h;
//	            i++; j--;
//	        }
//	    } while (i<=j);
//
//	    // recursion
//	    if (lo<j) quicksort(a, lo, j);
//	    if (i<hi) quicksort(a, i, hi);
//	    return a;
//	}
//	    
//	    public static void main(String args[]){
//	        int s[];
//	        s=new int[10000];
//	        
//	        Random a = new Random();
//	        for(int i=0;i<10000;i++)
//	        s[i]=a.nextInt(5000000); // Random generate 1000 integers.
//	        Time_record record=new Time_record();
//	        
//
//	        int temp[];
//	                 
//	     
//	                 
//	        
//	        
//	       
//	        
//	         record.begin();
//	         Sort.bubble_sort(s);
//	         record.end();    
//	        
//	        record.begin();
//	        Sort.select_sort(s);
//	        record.end();
//	       
//	        record.begin();
//	        Sort.insert_sort(s);
//	        record.end();
//	       
//	       
//	        record.begin();
//	        Sort.shell_sort(s);
//	        record.end();
//	        
//	        record.begin();    
//	        Sort.merge_sort(s);
//	        record.end(); 
//	        
//	        record.begin();
//	        Sort.quick_sort(s);    
//	        record.end(); 
//	            
//	    }    
//
//	 
//	}
//	
//}
